package leetcode;

import java.util.*;

public class Lc399 {

    HashMap<String, List<String>> map = new HashMap<>();
    HashMap<String, Double> res = new HashMap<>();

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {

        for (int i = 0; i < equations.size(); i++) {
            String a = equations.get(i).get(0);
            String b = equations.get(i).get(1);
            List<String> list = map.getOrDefault(a, new ArrayList<>());
            list.add(b);
            map.put(a, list);
            list = map.getOrDefault(b, new ArrayList<>());
            list.add(a);
            map.put(b, list);
            res.put(a + "&" + b, values[i]); // a - > b
            res.put(b + "&" + a, 1.0 / values[i]); // b -> a
        }

        double[] ans = new double[queries.size()];
        LinkedList<String> queue = new LinkedList();
        for (int i = 0; i < queries.size(); i++) {
            String a = queries.get(i).get(0);
            String b = queries.get(i).get(1);
            String temp = a + "&" + b;
            if (res.containsKey(temp)) {
                ans[i] = res.get(temp);
                continue;
            }
            if (!map.containsKey(a) || !map.containsKey(b)) {
                ans[i] = -1.0;
                continue;
            }
            if (a.equals(b)) {
                ans[i] = 1.0;
                continue;
            }
            ans[i] = getResult(a, a, b, new HashSet<String>(), 1.0);
        }
        return ans;
    }

    //DFS
    public double getResult(String root, String a, String b, HashSet set, double x) {
        if (set.contains(a)) return -1.0;
        List<String> list = map.get(a);
        if (list == null) return -1.0;
        set.add(a);
        for (int i = 0; i < list.size(); i++) {
            String c = list.get(i);
            if (set.contains(c)) continue;
            if (c.equals(b)) {
                String key = root + "&" + b;
                res.put(key, x * res.get(a + "&" + b));
                return x * res.get(a + "&" + b);
            }
            double temp = getResult(root, c, b, set, x * res.get(a + "&" + c));
            if (temp > 0) {
                return temp;
            }
        }
        return -1.0;
    }















}
